class Solution {//leetcode433——最小基因变化
private:
    char gen[4]={'A','C','G','T'};
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_map<string,bool> s_hash;
        unordered_map<string,bool> b_hash;
        int n=startGene.size(),step=0;
        s_hash[startGene]=true;
        for(auto& str:bank){
            b_hash[str]=true;
        }
        queue<string> q;
        q.push(startGene);
        //bfs
        while(q.size()){
            int cnt=q.size();
            step++;
            while(cnt--){
                string& cur=q.front();
                for(int i=0;i<n;i++){
                    for(int j=0;j<4;j++){
                        string tmp=cur;
                        tmp[i]=gen[j];
                        if(!s_hash.count(tmp)&&b_hash.count(tmp)){
                            if(tmp==endGene) return step;
                            q.push(tmp);
                            s_hash[tmp]=true;
                        }
                    }
                }
                q.pop();
            }
        }
        return -1;
    }
};